package org.agile4j.math.tree.bfs;

import java.util.*;

/**
 * 用队列实现 广度优先搜索
 *
 * @author hanyx
 * @date 2019/01/14
 */
public class BfsTree {

    /**
     * 广度优先搜索
     *
     * @param userNum     用户数量
     * @param relationNum 好友数量
     * @return
     */
    public static Node[] demoData(int userNum, int relationNum) {
        Node[] userNodes = new Node[userNum];
        // 生成用户节点
        for (int i = 0; i < userNum; i++) {
            userNodes[i] = new Node(i);
        }

        Random random = new Random();
        // 生成用户好友关系
        for (int i = 0; i < relationNum; i++) {
            int friendAId = random.nextInt(userNum);
            int friendBId = random.nextInt(userNum);
            if (friendAId == friendBId) {
                continue;
            }
            Node friendA = userNodes[friendAId];
            Node friendB = userNodes[friendBId];

            friendA.friends.add(friendBId);
            friendB.friends.add(friendAId);

        }
        return userNodes;
    }

    /**
     * 通过广度优先查找好友
     *
     * @param userNodes 用户的节点
     * @param userId    指定的用户ID,要给此用户查找好友
     */
    public static void bts(Node[] userNodes, int userId) {
        // 防止数组越界
        if (userId > userNodes.length) {
            return;
        }
        // 用于广度优先搜索的队列
        Queue<Integer> queue = new LinkedList<>();
        // 放入初始节点
        queue.offer(userId);

        // 存放已经被访问过的结点,防止回路
        Set<Integer> visited = new HashSet<>();
        visited.add(userId);

        while (!queue.isEmpty()) {
            // 拿出队列头部第一个节点
            int currentUserId = queue.poll();
            if (userNodes[currentUserId] == null) {
                continue;
            }

            // 遍历刚刚拿出去的这个节点的所有直接连接节点,并加入队列尾部
            for (int friendId : userNodes[currentUserId].friends) {
                if (userNodes[friendId] == null) {
                    continue;
                }
                if (visited.contains(friendId)) {
                    continue;
                }

                queue.offer(friendId);
                // 记录已经访问过的节点
                visited.add(friendId);
                // 好友的度数时是当前节点的好友度数再加1
                userNodes[friendId].degree = userNodes[currentUserId].degree + 1;
                System.out.println(String.format("\t用户id: %d 的 %d 度好友id: %d", userId, userNodes[friendId].degree, friendId));
            }
        }
    }

    /**
     * 通过 双向广度优先搜索,查找两个人之间最短关系长度
     *
     * @param userNodes 用户节点集合
     * @param userIdA   用户a
     * @param userIdB   用户b
     * @return 距离
     */
    public static int biBfs(Node[] userNodes, int userIdA, int userIdB) {
        // 防止数组越界异常
        if (userIdA > userNodes.length || userIdB > userNodes.length) {
            return -1;
        }

        // 两个用户是同一个人 返回0
        if (userIdA == userIdB) {
            return 0;
        }

        // 队列a, 用于从用户a出发的 广度优先搜索
        Queue<Integer> queueA = new LinkedList<>();
        // 队列b, 用于从用户b出发的 广度优先搜索
        Queue<Integer> queueB = new LinkedList<>();

        // 放入初始节点
        queueA.offer(userIdA);
        // 存放已经访问过的节点
        Set<Integer> visitedA = new HashSet<>();
        visitedA.add(userIdA);

        // 存放初始节点
        queueB.offer(userIdB);
        // 存放已经访问过的节点
        Set<Integer> visitedB = new HashSet<>();
        visitedB.add(userIdB);

        int degreeA = 0;
        int degreeB = 0;
        // 防止两者之间不存在通路
        int maxDdegree = 20;

        while (degreeA + degreeB < maxDdegree) {
            
        }

        return -1;
    }

    public static void main(String[] args) {
        Node[] testData = BfsTree.demoData(10, 15);
        for (Node node : testData) {
            System.out.print("userId: " + node.userId);
            System.out.print(", degree: " + node.degree);
            System.out.print(", friends: " + node.friends);
            System.out.println();
        }
        bts(testData, 6);
    }
}
